import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-21
 * Time: 16:08
 */
public class Solution {
    //二分查找
    private int binarySearch(int[]arr,int x){
        int begin=0;
        int end=arr.length-1;
        while(begin<=end){
            int mid=(begin+end)>>1;
            if(arr[mid]<x){
                begin=mid+1;
            }else if(arr[mid]==x){
                return mid;
            }else{
                end=mid-1;
            }
        }
        return end;
    }
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list=new ArrayList<>();
        int left=binarySearch(arr,x);
        int right=left+1;
        int length=arr.length;
        if(length<=k){
            for(int i=0;i<length;i++){
                list.add(arr[i]);
            }
            return list;
        }
        //因为要按顺序输出,所以先记录下标的范围,最后再add
        while(right-left-1<k){
            if(right>=length){
                left--;
            }else if(left<0){
                right++;
            }else{
                if(Math.abs(arr[left]-x)<=Math.abs(arr[right]-x)){
                    left--;
                }else{
                    right++;
                }
            }
        }
        for(int i=left+1;i<right;i++){
            list.add(arr[i]);
        }
        return list;
    }
}
